#!/usr/bin/python

""" Since the list is not hashable in the graph search, I change to tuple"""

from utils import *
from search_inver import *
#from collections import defaultdict

clock = [
1,
2,
5,
0,
100,
8,
3,
6,
7]

should = [1, 2, 5, 0, -1, 8, 3, 6, 7]

class EightPuzzle(Problem):
    """The problem of solving a eight puzzle problem """
    def __init__(self, state, d_dict):
        self.initial = tuple(state)
        self.invert_cnt = 0
        self.strict_invert_cnt = 0;
        self.expand_cnt = 0
        self.visit_cnt = 0
        self.d_dict = d_dict
                
    def successor(self, state):
        """In the 8 puzzle problem, move the blank to other position."""
        result = []
        position = list(state).index(0) 
        for action, newposition in self.possible_position(position).iteritems():
            new = list(state[:])
            new[newposition], new[position] = new[position], new[newposition]
            result.append((action, tuple(new)))
        return result
        
    def possible_position(self, position):
        """return the possible position"""
        result = {};
        col = position % 3;
        row = position // 3;
        # add the action in a circle manner. No dead iter now
        if row != 2:
            result['D'] = position +3
        if col != 0: 
            result['L'] = position -1   
        if row != 0:
            result['U'] = position -3
        if col != 2:
            result['R'] = position +1
        return result

    def goal_test(self, state):
        if state[0] != 0:
            return False
        elif state[1] !=1:
            return False
        elif state[2] !=2:
            return False
        elif state[3] !=3:
            return False
        elif state[4] !=4:
            return False
        elif state[5] !=5:
            return False
        elif state[6] !=6:
            return False
        elif state[7] !=7:
            return False
        elif state[8] !=8:
            return False
        else:
            #print state
            return True     
            # print state
    
    def manhattan(self, node):
        #print "This is M@@@@@"
        sum=0
        state = node.state
        for x in range(9): # mahatten distance
            pile = state[x]
            if pile == 0:
                continue
            row_delta = abs(pos[x][0] - pos[pile][0] )
            col_delta = abs(pos[x][1] - pos[pile][1] )
            sum += (row_delta + col_delta)
        #print "M in instance is", sum
        return sum

    def hn(self, node):
        """Plus the Nilsson sequence"""
        temp = list(node.state)
        s=0
        for i in xrange(9):
            if i != 4:
                if temp[clock[i]] != should[i]:
                    s+=2
        if temp[4]!=4:
            s+=1
        #print self.h(node)
        return self.h(node) + 3 *s
    
    def h2(self, node):
        t = self.h(node)
        if self.d_dict[node.state] > t:
            return t+1
        return t
        
    def getvalues(self, key):
   
        values = [1, -1, self.nsize, -self.nsize]
        valid = []
        for x in values:
            if key + x in range(0, self.tsize):
                if x == 1 and key in range(self.nsize - 1, self.tsize, 
                    self.nsize):
                    continue
                if x == -1 and key in range(0, self.tsize, self.nsize):
                    continue
                valid.append(x)
        return valid
        
    def expand(self, st):
        """Provide the list of next possible states from current state."""

        pexpands = {}
        for key in range(self.tsize):
            pexpands[key] = self.getvalues(key)
        pos = st.index(0)
        moves = pexpands[pos]
        expstates = []
        for mv in moves:
            nstate = st[:]
            (nstate[pos + mv], nstate[pos]) = (nstate[pos], nstate[pos + 
                    mv])
            expstates.append(nstate)
        return expstates
        
def all_perms(l):
    if len(l) <=1:
        yield l
    else:
        for perm in all_perms(l[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + l[0:1] + perm[i:]

mapping = {0:0, 1:1, 2:2, 3:5, 4:4, 5:3, 6:6, 7:7, 8:8}

pos = {0:[0, 0], 1:[0, 1], 2:[0,2], 3:[1, 0], 4:[1,1], 5:[1,2], 6:[2, 0], 7:[2,1], 8:[2, 2]}

clock = [1, 2, 5, 0,-1, 8, 3, 6, 7]

should = [1, 2, 5, 0, -1, 8, 3, 6, 7]

def solvable(l):
    newl = [l[mapping[i]] for i in xrange(9) if l[mapping[i]]!=0]
    #print newl
    return oddreverse(newl)
        
def oddreverse(l):
    #print l
    t = len(l)
    count = 0
    for i in xrange(t):
        for j in xrange(i):
            if l[j]>l[i]:
                count +=1
    if count%2 ==0:
        return False
    return True     
            

import cPickle

def getfullset():
    if os.path.exists("fullset"):
        f = open('fullset', 'rb')
        return cPickle.load(f)
    else:
        init = [i for i in xrange(9)]
        fullset = [tuple(state) for state in all_perms(init) if solvable(state)]
        print "After generation", len(fullset)
        output = open('fullset', 'wb')
        cPickle.dump(fullset, output)
        return fullset

"""     
def manhattan(state):
    sum=0
    for x in range(9): # mahatten distance
        pile = state[x]
        row_delta = abs(pos[x][0] - pos[pile][0] )
        col_delta = abs(pos[x][1] - pos[pile][1] )
        sum += (row_delta + col_delta)
    return sum
""" 
if (__name__=="__main__"):
    pkl_file = open('newninepuzzle', 'rb')
    d = cPickle.load(pkl_file)
    solved = set([i for i in d.iterkeys()])
    #full = set(getfullset())
    flag = True
    counter = 0
    """
    while flag:
        if len(solved) == len(full):
            print "Done"
            output = open('ninepuzzle', 'wb')
            cPickle.dump(d, output)
            print "Dump d", len(d)
            break
            #exit(0)    
        unsolved = full - solved
        state = unsolved.pop()
        print "Going to solve", state
        instance = EightPuzzle(state)
        a = astar_search(instance, instance.h)
        print "Solved"
        
        t = len(a.path())
        for i, j in enumerate(a.path()):
            if tuple(j.state) not in solved:
                counter +=1
                d[j.state] = i
                solved.add(tuple(j.state))
            
        if counter>200:
            counter = 0
            output = open('ninepuzzle', 'wb')
            cPickle.dump(d, output)
            print "Dump d", len(d)  """
    print "Done reading"
    total_ratio = 0.0;
    sample_cnt = 100;
    dl = d.keys()
    for i in range(1,sample_cnt):
        rdn_id = random.randint(0,len(d)-1)
        rdn_state = dl[rdn_id]
        #print "Manhattan", rdn_state, 
        t =  d[rdn_state]
        print i,
        #
        #if t > 12:
        #    continue
        #print rdn_state
        instance = EightPuzzle( rdn_state , d )
        a = astar_search( instance , instance.manhattan )
        #a1 = len(a.path())
        #print "A:", a1
        #assert (len(a.path()) -1 == t)
        #print "Solve:",rdn_state, instance.strict_invert_cnt, instance.invert_cnt, \
        #   instance.visit_cnt, instance.expand_cnt, float(instance.strict_invert_cnt)/instance.expand_cnt  
        #total_ratio = total_ratio + float(instance.strict_invert_cnt)/instance.expand_cnt
        
        #print "Ours"
        instance2 = EightPuzzle( rdn_state , d )
        b = astar_search2( instance2 , d, instance2.manhattan )
        #b1 = len(b.path())
        #print "B", b1
        #assert (a1 == b1)
        print t,
        print instance2.visit_cnt, instance.visit_cnt, 1.0* instance2.visit_cnt/instance.visit_cnt
        total_ratio += 1.0 * instance2.visit_cnt/instance.visit_cnt
#        if instance2.visit_cnt < instance.visit_cnt:
        #print "Original",rdn_state, instance.visit_cnt,
        #print "New     ", instance2.visit_cnt,
        #print "d", d[rdn_state]
        #print "------------------------------"

        #print "Solve:",rdn_state, instance2.strict_invert_cnt, instance2.invert_cnt, \
        #   instance2.visit_cnt, instance2.expand_cnt, float(instance2.strict_invert_cnt)/instance2.expand_cnt  
        #total_ratio = total_ratio + float(instance2.strict_invert_cnt)/instance2.expand_cnt
        
    print "AVERAGE:", total_ratio/sample_cnt